#include<stdio.h>
#include<stdlib.h>
#include"DCLinkList.h"
#define true 1
#define false 0

int InitDCLinkList(DCLlist *list)
{
    list->len=0;
    list->head=NULL;
    list->tail=NULL;
    return true;
}

struct Node *CreateNode(ElementType element)
{
    struct Node *newNode=(struct Node *)malloc(sizeof(struct Node));
    if(newNode==NULL)
    {
        printf("createNode malloc error!\n");
        return NULL;
    }

    newNode->data=element;
    newNode->next=NULL;
    newNode->prev=NULL;
    return newNode;
}

void InsertTail(DCLlist *list, ElementType element)
{
    struct Node *newNode=CreateNode(element);
    if(newNode==NULL)
    {
        printf("insert CreateNode error!\n");
        return;       
    }
    if(list->len==0)
    {
        list->head=newNode;
        list->tail=newNode;
    }
    else
    {
        list->tail->next=newNode;
        newNode->prev=list->tail;
        list->tail=newNode;
        //头尾相连
        newNode->next=list->head;
        list->head->prev=newNode;
    }
    list->len++;
}

void InsertHead(DCLlist *list, ElementType element)
{
    InsertTail(list,element);
    if(list->len!=1)
    {
        list->head=list->tail;
        list->tail=list->tail->prev;
    }
}

void FreeDLinklist(DCLlist *list)
{
    if(list->len==0)
        return;
    list->tail->next=NULL;
    while(list->head!=NULL)
    {
        struct Node *temp=list->head->next;
        free(list->head);
        list->head=temp;
    }
    list->len=0;
    list->head=NULL;
    list->tail=NULL;
}

void RemoveByIndex(DCLlist *list, int index)
{
    if(index<0 || index>=list->len)
    {
        printf("invalid space!\n");
        return;
    }

    if(index==0)
    {
        if(list->len==1)
        {
            free(list->head);
            list->head=NULL;
            list->tail=NULL;
            list->len--;
            return;
        }
        struct Node *temp=list->head;
        list->head=list->head->next;
        list->head->prev=list->tail;
        list->tail->next=list->head;
        free(temp);
        list->len--;
        return;
    }

    if(index==list->len-1)
    {
        struct Node *temp=list->tail;
        list->tail=list->tail->prev;
        list->tail->next=list->head;
        list->head->prev=list->tail;
        free(temp);
        list->len--;   
        return;    
    }

    struct Node *TravelPoint=list->head;
    while(index!=0)
    {
        TravelPoint=TravelPoint->next;
        index--;
    }
    // struct Node *PrevNode=TravelPoint->prev;
    // struct Node *NextNode=TravelPoint->next;
    TravelPoint->prev->next=TravelPoint->next;
    TravelPoint->next->prev=TravelPoint->prev;
    free(TravelPoint);
    list->len--;
}

void RemoveByElement(DCLlist *list, ElementType element)
{
    int count=FindFirstByElement(list,element);
    while(count!=-1)
    {
        RemoveByIndex(list,count);
        count=FindFirstByElement(list,element);
    }
}

int FindFirstByElement(DCLlist *list,ElementType element)
{
    int count=-1;
    struct Node *TravelPoint=list->head;
    while(TravelPoint!=list->tail)
    {
        if(TravelPoint->data==element)
        {
            return count+1;
        }
        count++;
        TravelPoint=TravelPoint->next;
    }
    if(list->tail!=NULL && list->tail->data==element)
    {
        return count+1;
    }
    return -1;
}

void Travel(DCLlist *list)
{
    if(list->len==0)
    {
        printf("the linklist is empty!\n");
        return;
    }
    printf("next: ");
    struct Node *TravelPoint=list->head;
    while(TravelPoint!=list->tail)
    {
        printf("%d ",TravelPoint->data);
        TravelPoint=TravelPoint->next;
    }
    printf("%d ",list->tail->data);
    printf("\n");

    printf("prev: ");
    TravelPoint=list->tail;
    while(TravelPoint!=list->head)
    {
        printf("%d ",TravelPoint->data);
        TravelPoint=TravelPoint->prev;
    }
    printf("%d ",list->head->data);
    printf("\n");
}

